Dilworth's theorem states that the length of a longest antichain in a partially ordered set $S$ is equal to the size of a minimum partition of $S$ into chains

If the poset is represented as a directed acyclic graph, the minimum partition into chains is equivalent to the vertex-disjoint path cover problem.

Note: Posets are transitive by nature. If a poset is represented in compressed form as a DAG, then the transitive closure must be taken before computing the vertex-disjoint path cover.

Problems

• Fat Hobbits
• Nested Dolls
• Incubator¹
• Gentrification
• Birthday²

See also

• Vertex-disjoint path cover
• Hall's marriage theorem

External links

• Dilworth's theorem
• Partially Ordered Sets